/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/symmetric-tree
   @Language: C++
   @Datetime: 19-07-15 10:52
   */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

// Method 1, postorder
class Solution {
	bool postorder(TreeNode *l, TreeNode *r){
		if(l==NULL && r==NULL) return true;
		if(l==NULL || r==NULL) return false;
		return l->val==r->val && postorder(l->left,r->right) && postorder(l->right,r->left);
	}
public:
	bool isSymmetric(TreeNode* root) {
		return postorder(root,root);
	}
};

// Method 2, loop
class Solution {
public:
	bool isSymmetric(TreeNode* root) {
		queue<TreeNode*> l, r;
		for(l.push(root),r.push(root); l.size() && r.size(); l.pop(), r.pop()){
			TreeNode *a=l.front(), *b=r.front();
			if(a==NULL && b==NULL) continue;
			if(a==NULL || b==NULL) return false;
			if(a->val != b->val) return false;
			l.push(a->left);
			l.push(a->right);
			r.push(b->right);
			r.push(b->left);
		}
		return true;
	}
};
